package org.forever.util
{
	/**
	* （有向）图的广度优先遍历算法模板
	*/
	public class DFS extends GraphTraverse
	{
		/**遍历过程中使用的计时钟*/
		public static var clock:int = 0;
		
		public function DFS(g:Graph)
		{
			super(g);
		}
		
		/**深度优先遍历算法*/
		override protected function traverse( v:Vertex,  info:Object):Object {///从顶点v出发，做深度优先查找
			if (UNDISCOVERED != v.getStatus())	return null;//跳过已访问过的顶点（针对非连通图）
			v.setDStamp(clock++);		
			v.setStatus(DISCOVERED);
			visit(v, info);//访问当前顶点
			for (var it:Iterator = v.getOutEdges(); it.hasNext();) {//检查与顶点v
				var e:Edge = it.getNext() as Edge;//通过边e = (v, u)
				var u:Vertex = e.getVPosInV(1).getElem() as Vertex;//相联的每一顶点u
				switch (u.getStatus()) {//根据u当前的不同状态，分别做相应处理
					case	UNDISCOVERED ://若u尚未被发现，则
						e.setType(TREE);//e被归类为“树边”
						traverse(u, info);//从u出发，继续做深度优先查找
						break;
					case	DISCOVERED ://若u已经被发现，但对其访问尚未结束，则
						e.setType(BACKWARD);//将e归类为“后向跨边”
						break;
					default ://VISITED，即对u的访问已经结束
						if (u.getDStamp() < v.getDStamp())//若相对于v，u被发现得更早，则
							e.setType(CROSS);//将e归类为“横跨边”
						else//否则
							e.setType(FORWARD);//将e归类为“前向跨边”
						break;
				}
			}//至此，v的所有邻居都已访问结束，故
			v.setFStamp(clock++);	
			v.setStatus(VISITED);//将v标记为VISITED
			return null;//然后回溯
		}
		
	}
}